﻿#pragma once
#include"stdafx.h"

/*
寻找两个正序数组的中位数  困难
给定两个大小为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。

请你找出这两个正序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。

你可以假设 nums1 和 nums2 不会同时为空。


 示例 1:

 nums1 = [1, 3]
 nums2 = [2]

 则中位数是 2.0
 示例 2:

 nums1 = [1, 2]
 nums2 = [3, 4]

 则中位数是 (2 + 3)/2 = 2.5


 解题思路：传统想法并归，然后使用总数的奇偶数，直接来找中位数，时间复杂度O(m+n)
 不满足题目要求呀，如果省去并归，自接通过最开始的数据大小来，只要找到第k个大的数据（奇偶数判断），
 就是对应是数据，但是通过分析，时间复杂度依旧是O(m+n)，依旧比 O(log(m + n)) 数据量大，
 恩恩，那我不一个一个对着比，而是采用二分来判断，只要判断出具体的位置便不就可以了么。
 这样的话时间复杂度就是O(log(m + n))，也就满足题目要求。思考问题循序渐进才会学到更多东西。
*/


int findMedNum(const vector<int>& nums1, const vector<int>& nums2, int k)
{
	int m = nums1.size();
	int n = nums2.size();
	int indexM = 0, indexN =0;
	while (true)
	{
		// 边界情况
		if (indexM == m)
		{
			return nums2[indexN + k -1];
		}
		if (indexN == n)
		{
			return nums1[indexM + k -1];
		}

		if (k == 1)
		{
			return min(nums1[indexM], nums2[indexN]);
		}

		//正常情况
		int newIndexM = min(indexM +k/2-1,m-1);
		int newIndexN = min(indexN +k/2-1,n-1);
		if (nums1[newIndexM] <= nums2[newIndexN])
		{
			k -= newIndexM - indexM + 1;
			indexM = newIndexM + 1;
		}
		else
		{
			k -= newIndexN - indexN + 1;
			indexN = newIndexN + 1;
		}
	}

}

double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) 
{
	int sumLength = nums1.size() + nums2.size(); //判断总数
	if ( (sumLength & 0x01) == 1) //当为奇数
	{
		return findMedNum(nums1, nums2,(sumLength+1)/2);
	}
	else //为偶数时候
	{
		return (findMedNum(nums1, nums2, sumLength / 2) + findMedNum(nums1, nums2, sumLength / 2 + 1)) / 2.0;
	}

}



